COMMENT ⊗   VALID 00006 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	Exercise
C00007 00003	Write a program to pretend to be a therapist, reading sentences in English from
C00008 00004
C00011 00005	A convex polygon of  N sides can be cut into N-2 triangles in a number of ways,
C00012 00006	Exercise, dynamic programming.
C00013 ENDMK
C⊗;
Exercise

Given a two-dimensional grid, as shown below, using array coordinates, and given
the real coordinate pairs (A1,B1) and A2,B2) of two points P1 and P2 in the region,
we want to record in an array the set of squares through which the straight line
segments from P1 and P2 passes.

Write a program to pretend to be a therapist, reading sentences in English from
the terminal. If an input sentence contains "am", the program should respond by
a confirmation, changing "am" to "are", "I" to "you", etc.:

Input: I am angry.
Output: You say you are angry.

It should respond to sentences containing family names, like "brother", with
"Tell me more about your family."

It should respond to "I don't like (trust, etc.) you" with "I'm only trying to
help you." If al else fails, it should say "Yes," or "Go on," or the like.



The input:				The desired character array.
A1=1.3, B1=2.5,				Image[2,3]=`*'
A2=5.4, B2=6.6				Image[2,4]=`*', etc.

A procedure to do this task can be used in a program to print crude line
drawings using a standard line (character) printer or a character-based
terminal screen.

The line through P1 and P2 passes through a particular square if it goes above
at least one of the four corners, and below at least one.
























As the illustration above shows, when B1<B2, the point (A,B) falls 
above the line if A>A1+(B-B1)(A2-A1)/(B2-B1), and below the line if 
A<A1+(B-B1)(A2-A1)/(B2-B1).

Here is a proposed Pascal program to put the line segment into a page image
and print it.

(Declarations)

PROCEDURE ABOVE(VERT,HORIZ:REAL):BOOLEAN;
	BEGIN
	ABOVE:=VERT>A1+(HORIZ-B1)*(A2-A1)/(B2-B1)
	END;

PROCEDURE BELOW(VERT,HORIZ:REAL):BOOLEAN;
	BEGIN
	BELOW:=VERT<A1+(HORIZ-B1)*(A2-A1)/(B2-B1)
	END;

READ(A1,B1,A2,B2);
FOR R:=1 TO 132 DO
	FOR C:=1 TO 60 DO
		IF (ABOVE(R-1,C-1) OR ABOVE(R-1,C))
			AND (BELOW(R,C-1) OR BELOW(R,C))
		THEN IMAGE[R,C]:=`*'
		ELSE IMAGE[R,C]:=` ';
WRITEPAGE(IMAGE) 


Unfortunately, the program is incorrect, in at least two ways.  It fails if

	A1= 5, B1=17, A2= 5, B2=43, and also if
   	A1=17, B1= 5, A2=43, B2= 5.

Your task: find all errors and report them. Correct them.  Test the corrected
program, and submit with it, in legible and coherent English, a persuasive
argument that it now works on any values of A1,B1,A2,B2.

A convex polygon of  N sides can be cut into N-2 triangles in a number of ways,
as shown below:

















Design a program which, given the coordinates of the vertices, finds the
triangulation that minimizes the total length of the cuts.
Exercise, dynamic programming.























Any convex polygon can be divided into triangles, as shown above, usually in
many ways.  Given the coordinates of the vertices, find the triangulation that
uses the least ink.